package org.example.ch12;

import jdk.nashorn.internal.runtime.options.Option;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/maximum-subarray/
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分
 */
public class MaxSubArray {

    public static void main(String[] args) {
        int[] array = new int[]{-2,1,-3,4,-1,2,1,-5,4};
//        int result = solution1(array);
//        int result = solution2(array);
        int result = solution3(array);
        System.out.println("result:"+result);
    }

    /**
     * 暴力破解 时间复杂度是o(n^2)
     * 空间复杂度是O(1)
     * @param nums
     * @return
     */
    public static int solution1(int[] nums){
        int max=Integer.MIN_VALUE;
        int numSize = nums.length;
        for (int i = 0; i < numSize; i++) {
            int sum = 0;
            for (int j = i; j < numSize; j++) {
                sum+=nums[j];
                if(sum>max){
                    max=sum;
                }
            }
        }
        return max;
    }

    /**
     * 动态规划实现
     * 时间复杂度是O(n),空间复杂度是0(n)
     * @param nums  2,3,-6,2,4
     * @return
     */
    public static int solution2(int[] nums){

        int[] dp = new int[nums.length];
        dp[0]=nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
        }
        return Arrays.stream(dp).max().getAsInt();
    }


    /**
     * 贪心算法实现
     * @param nums 2,3,-6,2,4
     * @return
     */
    public static int solution3(int[] nums){
        int sum = 0;
        int result=Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum +=nums[i];
            result=Math.max(result,sum);
            System.out.println("每次的result:"+result);
            //如果sum<0.重新开始查找字符串
            if(sum<0){
                sum=0;
            }
        }
        return result;
    }
}
